1. Field of the Invention
The present invention generally relates to techniques for determining delays through datapath elements and, more particularly, to techniques for determining signal delays through stages of multi-stage datapath elements.
Logical units, such as an invertor, typically are elements which operate on each digital bit in a datapath individually. In such units, operations on one bit has little, if any, effect on the operation on another bit in the datapath. However, for high-speed multi-stage arithmetic units, such as multipliers and the like, an operation on one bit in a datapath is often dependent upon the results of an operation on other bits. For example, a typical multiplier might include a plurality of carry-save adders and a final ripple-adder. In such multipliers, a carry bit is often generated during an operation on a low order bit and, then, the carry bit is used in an operation on a higher order bit in the multiplier. Since the carry bit must propagate through all of the bits of the ripple adder, the processing time required by the rippler-adder depends, in part, on the number of bits in the numbers being multiplied.
To provide high frequency operation of arithmetic functional units, so-called pipelining stages can be inserted in the units. Although pipelining stages in arithmetic elements have numerous advantages, they also can increase latency times (the period of time required to completely process a word). In other words, because pipelining stages add additional processing steps to arithmetic elements, the elements require longer periods of time to process each individual word. Nevertheless, an arithmetic element's output frequency (i.e., the number of words processed per unit time) may be increased, despite increased latency, by the insertion of pipelining stages in the element. This result follows from the fact that pipelining stages permit an element to begin operating on the next word before the element completes processing of a previous word. Accordingly, although pipelining stages increase element latency times, they also increase the frequency of operation of arithmetic elements.
Thus, the use of pipelining stages necessitates making performance trade-offs between frequency and latency. To achieve optimal or near optimal performance, it is desirable to insert only the minimum number of pipeline stages needed to achieve a desired operating frequency. Stated somewhat differently, pipeline stages ordinarily should be inserted at maximal distances into a functional element.
Effective placement of pipeline stages in a multi-stage datapath element requires fairly accurate estimates of delays through the individual stages of the element. Furthermore, in order to minimize computational complexity, the placement technique should be relatively simple to implement. Accordingly, it is a primary object of the present invention to present a simple and effective technique for determining delays encountered in datapath elements.